#include<iostream>
#include"LinkList.h"
using std::cin;
//InitList
bool InitList(LinkList& L) {
    if (L != nullptr) {
        return false;
    }

    L = new LNode;
    L->data = 0;
    L->next = nullptr;
    return true;
}

//get Length
int GetLength(LinkList L) {
    LNode* p = L->next;
    int i = 0;
    while (p != nullptr) {
        i++;
        p = p->next;
    }

    return i;
}

//GetElem
LNode* GetElem(LinkList L, int i) {
    if (i < 1 || L == nullptr) {
        return nullptr;
    }

    LNode* p = L->next;
    for (int j = 0; j < i; j++) {
        p = p->next;
    }
    return p;
}

// LocateElem
LNode* LocateElem(LinkList L, ElemType e) {
    if (L == nullptr) {
        return nullptr;
    }

    LNode* p = L->next;
    while (p->data != e || p != nullptr)
    {
        p = p->next;
    }
    return p;
}

// Base Insert
bool BaseInsert(LNode* p, ElemType e) {
    if (p == nullptr) {
        return false;
    }

    LNode* q = new LNode;
    q->next = p->next;
    p->next = q;
    q->data = e;

    return true;
}
//
bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i < 0 || i > GetLength(L) || L == nullptr) {
        return false;
    }
    LNode* p = GetElem(L, i - 1);
    return BaseInsert(p, e);
}

//Another front Insert
bool ListFrontInsert(LinkList& L, int i, ElemType e) {
    if (i < 0 || i > GetLength(L) || L == nullptr) {
        return false;
    }

    LNode* p = GetElem(L, i - 1);
    LNode* q = new LNode;
    q->next = p->next;
    p->next = q;
    q->data = p->data;
    p->data = e;
    return true;
}

//Delete Node
bool ListDelete(LinkList& L, int i, ElemType& e) {
    if (i < 0 || i > GetLength(L) || L == nullptr) {
        return false;
    }

    LNode* p = GetElem(L, i - 1);
    LNode* q = p->next;
    p->next = q->next;

    delete q;
    return true;
}

// Head Insert
bool List_HeadInsert(LinkList& L) {
    if (L != nullptr) {
        return false;
    }

    if (!InitList(L)) {
        return false;
    }

    LNode* head = L->next;
    int temp = 0;
    while (1) {
        cin >> temp;
        if (temp == MyExit) {
            break;
        }
        LNode* p = new LNode;
        if (p == nullptr) {
            return false;
        }

        p->data = temp;
        p->next = head->next;
        head->next = p;
    }
    return true;
}

// Tail Insert
bool List_TailInsert(LinkList& L) {
    if (L != nullptr) {
        return false;
    }

    if (!InitList(L)) {
        return false;
    }


    LNode* tail = L->next;

    int temp = 0;
    while (1) {
        cin >> temp;
        if (temp == MyExit) {
            break;
        }

        LNode* p = new LNode;
        p->data = temp;
        p->next = tail->next;
        tail->next = p;
        tail = p;
    }
    return true;
}

// Circlate LinkList

bool InitCLinkList(LinkList& L) {
    if (!L) {
        return false;
    }
    L = new LNode;
    if (L == nullptr) {
        return false;
    }
    L->data = 0;
    L->next = L;
    return true;
}

//Double LinkList



//Init
bool InitDLinkList(DLinkList& L) {
    if (L != nullptr) {
        return false;
    }
    L = new DLNode;
    L->data = 0;
    L->next = nullptr;
    L->prior = nullptr;

    return true;
}

// DList_HeadInsert
bool DList_HeadInsert(DLinkList& L) {
    if (L == nullptr) {
        return false;
    }

    if (!InitDLinkList(L)) {
        return false;
    }
    DLNode* temp, * head = L->next;
    ElemType t = 0;
    while (true) {
        cin >> t;
        if (t == MyExit) {
            break;
        }

        temp = new DLNode;
        temp->data = t;
        temp->next = head->next;
        temp->prior = head;
        head->next = temp;
        if (temp->next != nullptr) {
            temp->next->prior = temp;
        }
    }
    return true;
}
// CDList_TailInsert
bool CDList_TailInsert(CDLinkList& L) {
    if (L == nullptr) {
        return false;
    }

    if (!InitDLinkList(L)) {
        return false;
    }
    DLNode* temp, * head = L->next;
    ElemType t = 0;
    while (true) {
        cin >> t;
        if (t == MyExit) {
            break;
        }

        temp = new DLNode;
        temp->data = t;
        temp->next = head->next;
        temp->prior = head;
        head->next = temp;
        temp->next->prior = temp;
    }
    return true;
}
bool InitCDLinkList(CDLinkList& L) {
    if (L != nullptr) {
        return false;
    }
    L = new DLNode;
    L->data = 0;
    L->next = L;
    L->prior = L;

    return true;
}

// Find front DLNode
DLNode* FindFrontDLNode(DLinkList& L, int i) {
    if (i < 1 || L == nullptr) {
        return nullptr;
    }

    int j = 0;
    DLNode* p = L->next;
    while (j < i - 1) {
        p = p->next;
    }
    return p;
}

DLNode* FindFrontCDLNode(CDLinkList& L, int i) {
    if (i < 1 || L == nullptr) {
        return nullptr;
    }

    int j = 0;
    DLNode* p = L->next;
    while (j < i - 1) {
        p = p->next;
    }
    return p;
}

bool BehindInsertDLNode(DLNode* p, ElemType e) {
    if (p == nullptr) {
        return false;
    }
    DLNode* t = new DLNode;
    t->data = e;
    if (p->next == nullptr) {
        p->next = t;
        t->next = nullptr;
        t->prior = p;
    }
    t->next = p->next;
    t->prior = p->next->prior;
    p->next = t;
    t->next->prior = t;
    return true;
}

bool BehindInsertCDLNode(DLNode* p, ElemType e) {
    if (p == nullptr) {
        return false;
    }
    DLNode* t = new DLNode;
    t->data = e;
    t->next = p->next;
    t->prior = p->next->prior;
    p->next = t;
    t->next->prior = t;
    return true;
}
// insert
bool DLinkListInsert(DLinkList& L, int i, ElemType e) {
    DLNode* p = FindFrontDLNode(L, i);
    return BehindInsertDLNode(p, e);
}

// Delete DLNode
bool DLinkLListDelete(DLinkList& L, int i, ElemType& e) {
    DLNode* p = FindFrontDLNode(L, i);
    DLNode* q = p->next;
    p->next = q->next;
    e = q->data;
    q->next->prior = p;
    delete q;
    return true;
}

#define MaxSize 50


